#include <string>
#include <iostream>
#include <vector>
using namespace std;
/*
给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

class Solution
{
public:
    string longestPalindrome(string s)
    {
        if (s.size() == 0)
            return "";
        vector<int> range(2, 0);
        for (int i = 0; i < s.size(); i++)
        {
            i = findLongest(s, i, range);
        }
        return s.substr(range[0], range[1] - range[0] + 1);
    }
    int findLongest(string str, int low, vector<int> &range)
    {
        int high = low;
        while (high < str.size() - 1 && str[high + 1] == str[low])
        {
            high++;
        }
        int ans = high;
        while (low > 0 && high < str.size() - 1 && str[low - 1] == str[high + 1])
        {
            low--;
            high++;
        }
        if (high - low > range[1] - range[0])
        {
            range[0] = low;
            range[1] = high;
        }
        return ans;
    }

    //Another
    int longestPalindromeSubseq2(string s)
    {
        int n = s.size();
        vector<int> dp(n);
        int Max = 0;
        for (int i = 0; i < n; i++)
        {
            dp[i] = 1;
            Max = 0;
            for (int j = i - 1; j >= 0; j--)
            {
                int tmp = dp[j];
                if (s[i] == s[j])
                {
                    dp[j] = Max + 2;
                }
                Max = max(tmp, Max);
            }
        }
        Max = 0;
        for (int i = 0; i < n; i++)
        {
            Max = max(Max, dp[i]);
        }
        return Max;
    }
};